/**
 * https://leetcode-cn.com/problems/maximal-rectangle/
 * 最大矩形
 * 给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。
 * @param matrix
 */
const maximalRectangle = (matrix: string[][]): number => {
  const row = matrix.length;
  // 如果没有值, 返回0
  if (row === 0) return 0;

  const col = matrix[0].length;

  const heights = new Array(col).fill(0);

  let max = 0;

  for (let i = 0; i < row; i++) {
    for (let j = 0; j < col; j++) {
      if (matrix[i][j] === "1") {
        heights[j] += 1;
      } else {
        heights[j] = 0;
      }
      // 求得的每一行都要求值
    }
    max = Math.max(max, largestRectangleArea(heights));
  }

  return max;
};

const largestRectangleArea = (heights: number[]): number => {
  // 寻找左右的最小值
  const len = heights.length;

  // 默认为-1, 默认是这个柱状图左边没有比它小的
  const left = new Array(len).fill(-1);

  //! right 默认为柱状图的长度, 方便计算最大矩形面积
  const right = new Array(len).fill(len);

  const stack: number[] = [];

  for (let i = 0; i < len; i++) {
    // 栈不为空并且栈顶大于当前的柱状图的高度, 那么该高度就是栈中的顶的右边的第一个比它小的
    while (stack.length && heights[stack[stack.length - 1]] >= heights[i]) {
      right[stack.pop()!] = i;
    }

    // 栈不为空, 此时栈顶就是当前柱子的高度左边的第一个比它小的
    if (stack.length) {
      left[i] = stack[stack.length - 1];
    }

    // 将该值的索引放入栈中
    stack.push(i);
  }

  let ans = 0;
  for (let i = 0; i < len; i++) {
    ans = Math.max(ans, (right[i] - left[i] - 1) * heights[i]);
  }

  return ans;
};

// console.log(largestRectangleArea([1, 0]))

const res = maximalRectangle([
  ["0", "1"],
  ["1", "0"],
]);
// const res = maximalRectangle([
//   ["1", "0", "1", "0", "0"],
//   ["1", "0", "1", "1", "1"],
//   ["1", "1", "1", "1", "1"],
//   ["1", "0", "0", "1", "0"],
// ]);

console.log(res);
